其他
引介 | Turboproof 证明系统初探
以太坊的状态数据正不受限制地快速增长,长此以往,将只有少数大型公司才能负担运行节点的成本。应 Alexey 的要求,本文描述了我对 turboproof 证明系统的理解,该技术未来有可能会应用在多种轻客户端上。
以太坊区块链的状态数据使用十六叉(hexary)帕特里夏树(patricia tree)(或简称 trie)来存储的。数据存储有两个层次:
地址树是从地址到账户数据的映射。 智能合约的数据也存储在一棵数据树中,该树就是由从 32 字节内存地址到 32 字节的值的映射构成的。
叶子节点:这些是(键后缀,值)对,它们始终是默克尔树的终端节点。 分支节点:内部节点,并且此节点及其所有子节点共享相同的前缀。每个分支节点有 17 个条目。前 16 个条目对应于子节点的键后缀的第一个半字节。如果存在,则第 17 个条目是与键前缀关联的值 扩展节点:“捷径节点”,让所有子节点共享一个公共前缀。有了扩展节点,就不会建出很多只有一个叶子的分支节点了。。
序列化值
(0x1234,0x0000)
和(0x4567,0x2222)
的证明:(0x1234,0x0000)
和(0x4567,0x2222)
的(键,值)对(键和值长度被缩短以使生成的图片更具可读性)表示子树的哈希值。
Turboproof
叶子节点的清单 哈希值的列表,与树的原始分支一一对应 “结构信息”,即仅使用提供的哈希和叶子如何重建树的指令列表。
LEAF
表示应从证明的叶子序列中弹出一个叶子节点;BRANCH(i)
规定需要创建一个新的分支节点,并且之前构造的节点应存储为新分支节点的第 i 个子节点。然后将新节点存储在堆栈中;ADD(i)
规定,应将堆栈顶部的节点设置为堆栈上位于其下方的分支节点的第 i 个子节点;EXTENSION(ext)
规定应将堆栈顶部的节点设置为扩展节点(在 geth 中又称shortNode
)的子节点,整个子树的前缀由半字节ext
的序列表示;HASH
是表示子树哈希值的节点。
一些例子
树
(0xcafecafe,0x0303030303030303),
(0xcafedeca,0x0202020202020202),
(0xdeadbee0,0x0404040404040404),
(0xdeadbee7,0x0101010101010101)
证明
0xcafecafe
和 0xcafedeca
的。不需要用到的两个叶子节点将被转化为哈希值。然后将证明序列化为:节点以深度优先的顺序序列化:
哈希也按深度优先顺序进行序列化。只有一个哈希值,代表 0xd*
子树用于重建树的指令集:
LEAF
LEAF
BRANCH(14)
ADD(13)
EXTENSION([0xa, 0xf, 0xe])
BRANCH(13)
HASH
ADD(14)
用户现在可以证明他们知道树的当前状态。他们可以将证明发送给中继器或任何想要确保用户知道他们自己状态的人。
重建树
LEAF
LEAF
BRANCH(14)
ADD(13)
EXTENSION([0xa, 0xf, 0xe])
BRANCH(13)
HASH
ADD(14)
Turboproof 的意义
致谢
(完)
(文内提供了许多超链接,请点击阅读原文到 EthFans 网站上获取)
原文链接:
https://medium.com/@gballet/turboproofs-light-clients-and-saving-private-eth1-487aaa9b386
作者: AGuillaume Ballet
翻译 & 校对: TrumanW & 阿剑
你可能还喜欢: